#pragma once
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

template<typename T>
class SegmentTree {
private:
	struct TreeNode {
		T sum, min, max;
		T tag;
		int pl;
		int pr;

		TreeNode* left;
		TreeNode* right;

		TreeNode() :sum(0), min(99999), max(-99999), tag(0), pl(0), pr(0), left(NULL), right(NULL) {}

		TreeNode(T sum, T min, T max, int pl, int pr, TreeNode* left, TreeNode* right) :sum(sum), min(min), max(max), pl(pl), pr(pr), left(left), right(right), tag(0) {  }

	};

	typedef struct TreeNode* TreeNodePtr;

	TreeNodePtr root;

	vector<T> data;

	inline TreeNodePtr ls(TreeNodePtr node) {
		return node->left;
	}

	inline TreeNodePtr rs(TreeNodePtr node) {
		return node->right;
	}

	void push_up(TreeNodePtr node);

	T sum(int L, int R);

	inline void addtag(TreeNodePtr root, int pl, int pr, T d);

	inline void push_down(TreeNodePtr root, int pl, int pr);

	void Tagtodata(TreeNodePtr root);

	void deleteTree(TreeNodePtr root);

	void Insert(TreeNodePtr& root, int pos, T val);

	TreeNode query(TreeNodePtr root, int pl, int pr, int L, int R);

	void update(TreeNodePtr root, int pl, int pr, int L, int R, T d);

	void build(TreeNodePtr& root, int pl, int pr);

	void Erase(TreeNodePtr& root, int pos);

	void Erase(TreeNodePtr& root, int L, int R);

	void InorderTraverse(const TreeNodePtr root);

	TreeNodePtr copy(TreeNodePtr root);

public:

	void InsertToTree(int pos, T val);

	TreeNode QueryInTree(int L, int R);

	void DeleteFromTree(int pos);

	void DeleteFromTree(int L, int R);

	void UpdateTheTree(int L, int R, T d);

	SegmentTree() : root(NULL) {}

	SegmentTree(int left_end, int right_end, T data[], int size);

	SegmentTree(int left_end, int right_end, vector<T>data);

	SegmentTree(SegmentTree& tree);

	~SegmentTree();

	TreeNodePtr GetRoot() { return root; }
	int Getpl() { return root->pl; }
	int Getpr() { return root->pr; }
	vector<T> GetData() { return data; }

	int GetAmount() { return root->pr - root->pl + 1; }

	void Traversal();

	friend ostream& operator<<(ostream& output, const TreeNode& Node) {
		output << "Pos:" << Node.pl << "-" << Node.pr << '\n' << "Min:" << Node.min << '\n' << "Max:" << Node.max << '\n' << "Sum:" << Node.sum << '\n' << '\n';
		return output;
	}
};

template<typename T>
void SegmentTree<T>::push_up(TreeNodePtr node) {
	node->max = max(ls(node)->max, rs(node)->max);
	node->min = min(ls(node)->min, rs(node)->min);
	node->sum = ls(node)->sum + rs(node)->sum;
}

template<typename T>
T SegmentTree<T>::sum(int L, int R) {
	T res = 0;
	for (int i = L; i <= R; i++) {
		res += data[i];
	}
	return res;
}

template<typename T>
inline void SegmentTree<T>::addtag(TreeNodePtr root, int pl, int pr, T d) {
	root->tag += d;
	root->max += d;
	root->min += d;
	root->sum += (pr - pl + 1) * d;
}

template<typename T>
inline void SegmentTree<T>::push_down(TreeNodePtr root, int pl, int pr) {
	if (root->tag != 0) {
		int mid = (pr + pl) >> 1;
		addtag(ls(root), pl, mid, root->tag);
		addtag(rs(root), mid + 1, pr, root->tag);
		root->tag = 0;
	}
}//push_down

template<typename T>
inline void SegmentTree<T>::Tagtodata(TreeNodePtr root) {
	if (root == NULL) return;
	if (root->tag != 0) {
		for (int i = root->pl; i <= root->pr; i++) {
			data[i] += root->tag;
		}
		root->tag = 0;
		return;
	}
	Tagtodata(root->left);
	Tagtodata(root->right);
}

template<typename T>
void SegmentTree<T>::deleteTree(TreeNodePtr root) {
	if (root != NULL) {
		deleteTree(root->left);
		deleteTree(root->right);
		delete root;
	}
}

template<typename T>
void SegmentTree<T>::Insert(TreeNodePtr& root, int pos, T val) {
	int pl = root->pl;
	int pr = root->pr + 1;
	deleteTree(root);
	root = NULL;
	data.insert(data.begin() + pos, val);
	build(root, pl, pr);
}

template<typename T>
typename SegmentTree<T>::TreeNode SegmentTree<T>::query(TreeNodePtr root, int pl, int pr, int L, int R) {
	TreeNode res;
	if (root == NULL) {
		return res;
	}
	if (L <= pl && R >= pr) {
		return *root;
	}
	push_down(root, pl, pr);
	int mid = (pr + pl) >> 1;
	if (L <= mid) {
		res.min = min(res.min, query(ls(root), pl, mid, L, R).min);
		res.max = max(res.max, query(ls(root), pl, mid, L, R).max);
		res.sum += query(ls(root), pl, mid, L, R).sum;
		res.pl = pl;
		res.pr = pr;
	}
	if (R > mid) {
		res.min = min(res.min, query(rs(root), mid + 1, pr, L, R).min);
		res.max = max(res.max, query(rs(root), mid + 1, pr, L, R).max);
		res.sum += query(rs(root), mid + 1, pr, L, R).sum;
		res.pl = pl;
		res.pr = pr;
	}
	return res;
}

template<typename T>
void SegmentTree<T>::update(TreeNodePtr root, int pl, int pr, int L, int R, T d) {
	if (root == NULL) return;
	if (L <= pl && R >= pr) {
		addtag(root, pl, pr, d);
		return;
	}
	push_down(root, pl, pr);
	int mid = (pl + pr) >> 1;
	if (L <= mid) update(ls(root), pl, mid, L, R, d);
	if (R > mid)  update(rs(root), mid + 1, pr, L, R, d);
	push_up(root);
}

template<typename T>
void SegmentTree<T>::build(TreeNodePtr& root, int pl, int pr) {
	if (root == NULL) root = new TreeNode;
	root->pl = pl;
	root->pr = pr;
	if (pr == pl) {
		root->min = data[pl];
		root->max = data[pl];
		root->sum = data[pl];
		return;
	}
	int mid = (pr + pl) >> 1;
	build(root->left, pl, mid);
	build(root->right, mid + 1, pr);
	push_up(root);
}

template<typename T>
void SegmentTree<T>::Erase(TreeNodePtr& root, int pos) {

	int pl = root->pl;
	int pr = root->pr - 1;
	deleteTree(root);
	root = NULL;
	data.erase(data.begin() + pos);
	build(root, pl, pr);
}

template<typename T>
void SegmentTree<T>::Erase(TreeNodePtr& root, int L, int R) {

	int pl = root->pl;
	int pr = root->pr - (R - L + 1);
	deleteTree(root);
	root = NULL;
	data.erase(data.begin() + L, data.begin() + R + 1);
	build(root, pl, pr);
}

template<typename T>
void SegmentTree<T>::InorderTraverse(const TreeNodePtr root) {
	if (root != NULL) {
		cout << *root;
		InorderTraverse(root->left);
		InorderTraverse(root->right);
	}
}

template<typename T>
typename SegmentTree<T>::TreeNodePtr SegmentTree<T>::copy(typename SegmentTree<T>::TreeNodePtr root) {
	if (root == NULL) return NULL;
	TreeNodePtr left = NULL, right = NULL;

	if (root->left != NULL) {
		left = copy(root->left);
	}
	else left = NULL;
	if (root->right != NULL) {
		right = copy(root->right);
	}
	else right = NULL;

	TreeNodePtr newTree = new TreeNode(root->sum, root->min, root->max, root->pl, root->pr, NULL, NULL);
	newTree->left = left;
	newTree->right = right;
	return newTree;
}

template<typename T>
void SegmentTree<T>::InsertToTree(int pos, T val) {
	if (pos > root->pr + 1 || pos <= 0) return;
	Tagtodata(root);
	Insert(root, pos, val);
}

template<typename T>
typename SegmentTree<T>::TreeNode SegmentTree<T>::QueryInTree(int L, int R) {
	return query(root, root->pl, root->pr, L, R);
}

template<typename T>
void SegmentTree<T>::DeleteFromTree(int pos) {
	if (pos > root->pr + 1 || pos <= 0) return;
	Erase(root, pos);
}

template<typename T>
void SegmentTree<T>::DeleteFromTree(int L, int R) {
	if (R > root->pr + 1 || L <= 0) return;
	Erase(root, L, R);
}

template<typename T>
void SegmentTree<T>::UpdateTheTree(int L, int R, T d) {
	if (R > root->pr + 1 || L <= 0) return;
	update(root, root->pl, root->pr, L, R, d);
}

template<typename T>
SegmentTree<T>::SegmentTree(int left_end, int right_end, T data[], int size) {
	vector<T> tem(data, data + size);
	this->data = tem;
	tem.clear();
	build(root, left_end, right_end);
}

template<typename T>
SegmentTree<T>::SegmentTree(int left_end, int right_end, vector<T>data) {
	this->data = data;
	build(root, left_end, right_end);
}

template<typename T>
SegmentTree<T>::SegmentTree(SegmentTree& tree) {
	this->root = copy(tree.GetRoot());
	this->pl = tree.Getpl();
	this->pr = tree.Getpr();
	this->data = tree.GetData();
}

template<typename T>
SegmentTree<T>::~SegmentTree() {
	deleteTree(root);
	data.clear();
}

template<typename T>
void SegmentTree<T>::Traversal() {
	InorderTraverse(root);
}